package leetcode;
/**
 * 376.摆动序列
 * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
 * 第⼀个差（如果存在 的话）可能是正数或负数。少于两个元素的序列也是摆动序列.
 * 示例 1:
 * 输⼊: [1,7,4,9,2,5]
 * 输出: 6
 * 解释: 整个序列均为摆动序列。
 * 示例 2:
 * 输⼊: [1,17,5,10,13,15,10,5,16,8]
 * 输出: 7
 * 解释: 这个序列包含⼏个⻓度为 7 摆动序列，其中⼀个可为[1,17,10,13,10,16,8]。
 * 示例 3:
 * 输⼊: [1,2,3,4,5,6,7,8,9]
 * 输出: 2
 */
public class Num_376 {
    //贪心的思路：
    //局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），只保留峰值。
    //整体最优：整个序列有最多的局部峰值，从⽽达到最⻓摆动序列。
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = (prevdiff != 0) ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
}
